#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: min_depth.py 
@version:
@time: 2024/01/25

对于根节点来说，选择其左右子树中较深的子树的深度再加上根节点这一层的深度1，即为这棵二叉树的最大深度。可以将原问题拆分成不断求子树深度的问题。

求子树深度可以视为原始问题的子问题，在解决规模较大的问题前，需要先解决规模较小的子问题。
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node1.left = node2
node1.right = node3
node3.left = node4
node3.right = node5


def max_depth(root):
    if not root:
        return 0
    else:
        return max(max_depth(root.left), max_depth(root.right)) + 1


def min_depth(root):
    if not root:
        return 0
    if not root.left:
        return min_depth(root.right) + 1
    elif not root.right:
        return min_depth(root.left) + 1
    else:
        return min(min_depth(root.left), min_depth(root.right)) + 1


print(max_depth(node1))
print(min_depth(node1))
